package 题目集.动态规划.枚举行为优化;

import org.junit.Test;

/**
 * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/
 * 给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 */
public class ch02_股票问题4 {
	/**
	 * 由ch01可知，必须选第j个物品的最大值，依赖于dp1中最大的dp1[i]-price[i]。
	 *  dp[i][j]:最多卖出i次，仅有j个可选时的最大值 dp[i][j]
	 */
	public int maxProfit(int k, int[] prices) {
		int[][] dp = new int[2][prices.length + 1];
		int pre, cur = 0;
		for (int i = 1; i <= k; i++) {
			pre = cur;
			cur = (cur + 1) % 2;
			int depence=Integer.MIN_VALUE;
			for (int j = 1; j <= prices.length; j++) {
				depence=Math.max(dp[pre][j]-prices[j-1], depence);
				//dp[cur][j - 1]是左侧其他数拿k次的最大值
				dp[cur][j] = Math.max(depence+prices[j-1], dp[cur][j - 1]);
			}
		}
		return dp[cur][prices.length];
	}
	@Test
	public void test() {
		int k=2;
		int[] arr= {2,4,1};
		int res = maxProfit(k, arr);
		System.out.println(res);
	}
}
